package 剑指offer;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/27 11:17 星期六
 */
public class _53_2_0到n减1中缺失的数字 {
    public static void main(String[] args) {
        int[] num = new int[]{1};
        System.err.println(missingNumber3(num));
    }

    /**
     * 直接动态指针法
     * > 2022/08/27 11:23:09
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:42.1 MB,击败了53.71% 的Java用户
     *
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        int pointer = 0;
        for (int num : nums) {
            if (pointer++ != num) {
                return pointer - 1;
            }
        }
        return pointer;
    }

    /**
     * 累加和理论值减去实际和的值，有失偏颇，性能较差
     * > 2022/08/27 11:26:44
     * 解答成功:
     * 执行耗时:2 ms,击败了7.45% 的Java用户
     * 内存消耗:42.3 MB,击败了41.77% 的Java用户
     *
     * @param nums
     * @return
     */
    public static int missingNumber2(int[] nums) {
        return nums.length * (nums.length + 1) / 2 - Arrays.stream(nums).sum();
    }

    /**
     * 二分法效率还是蛮高的
     * > 2022/08/27 13:04:21
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:42 MB,击败了79.07% 的Java用户
     * @param nums
     * @return
     */
    public static int missingNumber3(int[] nums) {
        //定义二分法的左右指针
        int lp = 0;
        int rp = nums.length - 1;
        //当左指针不大于右指针，循环继续
        while (lp < rp) {
            //定义中间角标（防止溢出int范围）
            int mid = lp + (rp - lp) / 2;
            //若发现目标值比预测值大，说明它或它的左边界之间有问题
            if (nums[mid] > mid) {
                //缩短右边界（不能-1，因为不能确定边界是否是mid本身）
                rp = mid;
            } else {
                //否则，左侧完全合理，缩短左边界
                lp = mid + 1;
            }
        }
        //若循环结束，左指针的值等于左指针预测值，说明它和它左边都没问题，在右边加一个。否则，有问题，返回有问题的角标即可
        return nums[lp] == lp ? lp + 1 : lp;
    }
}
